package Hot100;

import java.util.PriorityQueue;
import java.util.Queue;

public class 数据流的中位数 {
    class MedianFinder {

        Queue<Integer> prePQ;
        Queue<Integer> aftPQ;

        public MedianFinder() {
            prePQ = new PriorityQueue<>((x, y) -> y - x);
            aftPQ = new PriorityQueue<>((x, y) -> x - y);
        }

        public void addNum(int num) {
            if (prePQ.isEmpty() || num <= prePQ.peek()) {
                prePQ.offer(num);
                if (aftPQ.size() + 1 < prePQ.size()) aftPQ.offer(prePQ.poll());
            } else {
                aftPQ.offer(num);
                if (prePQ.size() + 1 < aftPQ.size()) prePQ.offer(aftPQ.poll());
            }
        }

        public double findMedian() {
            if (prePQ.size() == aftPQ.size()) return ((double) prePQ.peek() + aftPQ.peek()) / 2;
            else return prePQ.size() > aftPQ.size() ? prePQ.peek() : aftPQ.peek();
        }
    }
}
